package dynamic;

import java.util.*;

public class Ex416 {
    class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0, len = nums.length;
            for(int n: nums) sum += n;
            if ((sum & 1) == 1) return false; //总和为奇数，肯定不满足
            //表示选择第i将物品能否使得当前和为j
            int target = sum >>> 1;
            boolean[][] f = new boolean[len][target + 1]; //只需达到总和的一半
            f[0][0] = false; //采用nums[0]去拼凑大小为0的结果是不可行的
            for (int i = 1; i < len; i++) {
                for (int j = target; j >= 0; j--) {
                    f[i][j] = f[i - 1][j];
                    if (f[i][j] || j == nums[i]) {
                        f[i][j] = true;
                        continue;
                    }
                    if (j > nums[i]) f[i][j] = f[i][j] || f[i - 1][j - nums[i]];
                }
            }
            return f[len - 1][target];
        }
    }
}
